package code.class3;

/**
 * https://leetcode.cn/problems/trapping-rain-water/
 * 接雨水问题
 * 与Code04_trapTrain不同的解决思路，使用双指针解决
 */
public class Code05_trapTrain02 {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 3, 9, 2, 4, 6, 8, 4, 2, 1};
        int trap = trap(arr);
        System.out.println("trap = " + trap);
    }


    /**
     * *  0 1 2 3 4 5 6 7
     * *  5 2 4 6 3 9 2 4
     * *  0 |         |n-1
     * *    l         r
     * *  lmax = arr[0]
     * *  rmax = arr[n-1];
     */
    public static int trap(int[] arr) {
        int n = arr.length;
        int ans = 0, lmax = arr[0], rmax = arr[n - 1];

        int l = 1, r = n - 2;
        while (l <= r) {
            // 判断左右哪个为边界
            if (lmax > rmax) {
                // 1.计算水量
                ans += Math.max(rmax - arr[r], 0);
                // 2.计算水量后，r位置与rmax进行比较，获得最大值
                rmax = Math.max(rmax, arr[r--]);
            } else {
                ans += Math.max(lmax - arr[l], 0);
                lmax = Math.max(lmax, arr[l++]);
            }
        }
        return ans;
    }
}
